Image segmentation is typically the first, and most difficult, task of any automated image understanding process. Segmentation refers to grouping of parts of an image that have "similar" image characteristics. All subsequent interpretation tasks, such as feature extraction, object detection, and object recognition, rely heavily on the quality of the segmentation process. Despite the large number of segmentation methods presently available, no general-purpose methods have been found which perform adequately across a diverse set of imagery. To date, the only effective method of using a given segmentation process is to manually modify the algorithm's control parameters until adequate results are achieved. Only after numerous modifications to an algorithm's control parameter set can any current segmentation technique be used to process the wide diversity of images encountered in real world applications such as the operation of an autonomous robotic land vehicle or aircraft, automatic target recognizer, or a photointerpretation task.
When presented with an image from one of these application domains, selecting the appropriate set of algorithm parameters is the key to effectively segmenting the image. The image segmentation problem can be characterized by several factors which make parameter selection process very difficult. First, most of the powerful segmentation methods available today contain numerous control parameters which must be adjusted to obtain optimal or peak performance. As an example, the Phoenix segmentation algorithm contains 14 separate control parameters that directly affect the segmentation results. (The Phoenix algorithm is described in "The Phoenix Image Segmentation System: Description and Evaluation," SRI International Technical Note No. 289, December, 1982.) The size of the parameter search space in these systems can be prohibitively large unless it is traversed in a highly efficient manner. Second, the parameters within most segmentation algorithms typically interact in a complex, non-linear fashion, which makes it difficult or impossible to model the parameters' behavior in an algorithmic or rule-based fashion. Thus, the multidimensional objective function which results from and defined by various parameter combinations generally cannot be modeled in a mathematical way. Third, since variations between images cause changes in the segmentation results, the objective function varies from image to image. The search method used to optimize the objective function must be able to adapt to these variations between images. Finally, the definition of the objective function itself can be subject to debate because there are no single, universally accepted measures of segmentation performance available with which to efficiently define the quality of the segmented image.
Known search and optimization techniques or methodologies which attempt to modify segmentation parameters have various drawbacks. For instance, exhaustive techniques (e.g., random walk, depth first, breadth first, enumerative) are able to locate global maximum but are computationally prohibitive because of the size of the search space.
Calculus-based techniques (e.g., gradient methods, solving systems of equations) have no closed form mathematical representation of the objective function available. Discontinuities and multimodal complexities are present in the objective function.
Partial knowledge techniques (e.g., hill climbing, beam search, best first, branch and bound, dynamic programming, A.sup.*) are inadequate. Hill climbing is plagued by the foothill, plateau, and ridge problems. Beam, best first, and A.sup.* search techniques have no available measure of goal distance. Branch and bound requires too many search points while dynamic programming suffers from the curse of dimensionality.
Knowledge-based techniques (e.g., production rule systems, heuristic methods) have a limited domain of rule applicability, tend to be brittle, and are usually difficult to formulate. Further, the visual knowledge required by these techniques may not be representable in knowledge-based formats.
Hence, a need exists to apply a technique that can efficiently search the complex space of plausible parameter combinations and locate the values which yield optimal results. The approach should not be dependent on the particular application domain nor should it have to rely on detailed knowledge pertinent to the selected segmentation algorithm. Genetic algorithms, which are designed to efficiently locate an approximate global maximum in a search space, have the attributes described above and show great promise in solving the parameter selection problem encountered in the image segmentation task.
Genetic algorithms are able to overcome many of the problems mentioned in the above optimization techniques. They search from a population of individuals (search points), which make them ideal candidates for parallel architecture implementation, and are far more efficient than exhaustive techniques. Since they use simple recombinations of existing high quality individuals and a method of measuring current performance, they do not require complex surface descriptions, domain specific knowledge, or measures of goal distance. Moreover, due to the generality of the genetic process, they are independent of the segmentation technique used, requiring only a measure of performance for any given parameter combination. Genetic algorithms are also related to simulated annealing where, although random processes are also applied, the search method should not be considered directionless. In the image processing domain, simulated annealing has been used to perform image restoration and segmentation. Simulated annealing and other hybrid techniques have the potential for improved performance over earlier optimization techniques.